package linkedList;

/**
 * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 * 如果有两个中间结点，则返回第二个中间结点。
 *
 * 给定链表的结点数介于 1 和 100 之间。
 */
public class MiddleOfLinkedList_876 {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        // 快指针每次走走两步，慢指针每次走一步，当快指针到达终点，慢指针到达中点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }
}
